public class NextPermutation {

    public void nextPermutation(int[] nums) {
        int n = nums.length;
        if (n == 1) return;
        int index = n - 1;
        while (index > 0) {
            if (nums[index] > nums[index - 1]) {
                break;
            }
            index--;
        }
        if (index == 0) {
            int l = 0;
            int r = n - 1;
            while (l < r) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                l++;
                r--;
            }
            return;
        }
        for (int i = n - 1; i >= index; i--) {
            if (nums[i] > nums[index - 1]) {
                int temp = nums[i];
                nums[i] = nums[index - 1];
                nums[index - 1] = temp;
                int l = index;
                int r = n -1;
                while (l < r) {
                    temp = nums[l];
                    nums[l] = nums[r];
                    nums[r] = temp;
                    l++;
                    r--;
                }
                return;
            }
        }
    }
}
